مسئله : 31 مهره هم شكل داريم ، اين مهره ها از نظر ظاهري هيچ تفاوتي با هم ندارند. اما مي‌دانيم كه 30 مهره از آن‌ها هم‌وزنند و يكي از مهره ها وزني متفاوت با 30 مهره ديگر دارد. يك ترازوي دو كفه‌اي نيز در اختيار داريم. توضيح دهيد كه چگونه مي‌توان حداكثر با 4 بار وزن كردن مهره نا خالص (مهره‌اي كه وزن متفاوت دارد) را پيدا كرد و تعيين نمود كه وزن آن از ديگر مهره‌ها كمتر است يا بيشتر.
پاسخ: در آغاز ممكن است مسئله كمي عجيب به نظر برسد. زيرا در مقايسه با اطلاعات ناچيز ما كه حتي نمي‌دانيم مهره‌ي ناخالص از ديگر مهره‌ها سنگين‌تر است يا سبك‌تر و تعداد ناخالص از ديگر مهره‌ها يعني 31 مهره ، 4 بار وزن كردن ظاهراً خيلي كم است. اگر هم دست به آزمايش بزنيم و سعي كنيم با روش آزمون و خطا الگوريتم حل مسئله را پيدا كنيم به احتمال زياد بعد از چند ساعت يا حتي چند روز كار بي‌حاصل از حل آن نا اميد خواهيم شد.
براي آنكه كار كمي ساده‌تر شود، صورت مسئله را كمي تغيير مي‌دهيم. سعي كنيد همان مسئله بالا را براي 10 مهره كه 9 مهره وزن يكسان و يكي وزني متفاوت دارد حل كنيد. اما اين بار فقط 3 بار مي‌توانيد از ترازوي دو كفه‌اي استفاده كنيد.
حالا كمي ساده‌تر شد و با كمي فكر احتمالاً مي‌توانيد جواب را پيدا كنيد. اگر خواستيد مقاله را همين جا رها كنيد و سعي كنيد خودتان اين مسئله جديد را حل كنيد. وقتي به جواب رسيديد ادامه‌ي مقاله را مطالعه كنيد.
بله، همان طور كه احتمالاً شما هم به نتيجه رسيديد اين كار ممكن است. كافي است 10 مهره را به 4 دسته تقسيم كنيم . در دسته‌هاي اول و دوم وسوم هر كدام سه مهره و در دسته‌ي چهارم يك مهره قرار مي‌دهيم . سپس با دوبار استفاده از ترازو يك بار مهره‌هاي دسته‌هاي اول و دوم و بار ديگر مهره‌هاي دسته‌هاي دوم و سوم را با هم مقايسه مي‌كنيم. به يكي از اين دو نتيجه ي زير خواهيم رسيد:
الف) يكي از دسته‌هاي اول ، دوم و يا سوم از دوم دسته‌ي ديگر سنگين‌تر يا سبك‌تر است.
ب) هر سه دسته‌ي اول ، دوم و سوم هم و زنند.
در حالت الف به سادگي خواهيم فهميد كه مهره‌ي ناخالص در همان دسته‌ي يا سبك‌تر است. مثلاً خواهيم دانست كه مهره‌ي نا خالص يكي از سه مهره دسته‌ي اول و از ساير مهره‌ها سنگين است. در اين صورت كافي است، براي سومين بار نيز از ترازو استفاده كرده و دو مهره از دسته‌ي اول را با هم مقايسه كنيم.
دو حالت رخ خواهد داد، يا دو مهره هم وزن خواهند بود كه در اين صورت مهره نا خالص مهره‌ي سوم و همان‌طور كه قبلاً فهميديم از ساير مهره‌ها سنگين‌تر است و يا يكي از دو مهره سنگين‌تر خواهد بود كه در اين صورت مهره‌ي سنگين‌تر همان مهره‌ي نا خالص است.
در حالت ب چون مهره‌ي نا خالص هيچ يك از 9 مهره‌ي موجود در دسته‌ي اول و دوم و سوم نيست، پس مهره‌ي نا خالص همان مهره‌ي موجود در دسته‌ي چهارم است. اما هنوز نمي‌دانيم اين مهره از ساير مهره‌ها سنگين‌تر است يا سبك‌تر. براي فهم اين مطلب كافي است براي بار سوم نيز از ترازو استفاده كرده و اين مهره را با يكي از 9 مهره‌ي ديگر مقايسه كنيم. و به اين ترتيب مسئله به طور كامل حل خواهد شد.
اما اين تازه آغاز كار بود. حال برگرديم سر 31 مهره. احتمالاً به اين مطلب پي برده‌ايد كه شروع كار باز مانند حالت قبل خواهد بود، يعني بايد مهره‌ها را با 4 دسته تقسيم كنيم كه دسته‌هاي اول و دوم و سوم مهره‌هايي با تعداد برابر داشته باشند و به خودي خود تعداد مهره‌ها در دسته چهارم متفاوت خواهد بود. سپس دسته‌هاي اول و دوم را با هم و دسته‌هاي دوم و سوم را باهم مقايسه مي‌كنيم. به اين ترتيب دوبار از ترازو استفاده شده است و يكي از دو حالت زير نتيجه خواهد شد: (كه در هر كدام از حالت‌ها فقط با دوبار استفاده از ترازو باي مهره‌ي نا خالص را يافته ، بگوييم از ديگر مهره‌ها سنگين‌تر است يا سبك‌تر)
حالت الف- يكي از دسته‌هاي اول، دوم و يا سوم از دو دسته ديگر سنگين‌تر است يا سبك‌تر.
حالت ب- هر سه دسته‌ي اول، دوم و سوم هم وزنند.
در حالت الف واضح است كه مهره نا خالص در همان دسته سنگين‌تر يا سبك‌تر قرار دارد، پس خواهيم فهميد كه مهره‌ي نا خالص مثلاً در دسته‌ي دوم قرار دارد و از ساير مهره‌ها سبك‌تر است. سئوالي كه در اين جا مطرح مي‌شود اين است كه در دسته‌ي دوم حداكثر چند مهره مي‌تواند باشد تا فقط با دو بار وزن كردن مهره‌ي نا خالص را پيدا كنيم؟
(البته با توجه به اين كه مي‌دانيم مهره‌ي نا خالص از ساير مهره‌ها سبك‌تر است)
جواب 9 مهره است. زيرا مي‌توان آن را به سه دسته‌ي سه تايي تقسيم كرد و دو دسته را هم مقايسه كرد. اگر هم وزن بودند مهره‌ي نا خالص در دسته‌ي سبك‌تر است. پس با يك بار وزن كردن خواهيم فهميد مهره نا خالص سبك‌تر نيز هست و با يك‌بار وزن كردن به سادگي مي‌توان مهره‌ي نا خالص را پيدا كرد. به اين شكل كه دو مهره را وزن مي‌كنيم اگر مساوي بودند مهره‌ي ناخالص مهره سوم است و اگر يكي سبك‌تر از مهره‌ي ديگر بود، مهره ناخالص همان مهره سبك‌تر است. تا اين جاي مسئله به اين نتيجه رسيديم كه در هر يك از دسته‌هاي اول، دوم و سوم بايد 9 مهره قرار مي‌دهيم. اما آيا در حالت ب يعني وقتي وزن دسته‌هاي اول، دوم و سوم برابر باشد و ما بفهميم مهره‌ي نا خالص يكي از اين 4 مهره است تنها با دوبار وزن كردن مي‌توانيم آن مهره را پيدا كنيم؟
(دقت كنيد كه در اين حالت ما هنوز نمي‌دانيم مهره ناخالص سبك‌تر است يا سنگين‌تر .لذا بايد سنگين‌تر يا سبك‌تر بودن آن را تعيين كنيم. در ضمن در اين حالت هر 27 مهره‌ي دسته‌هاي اول، دوم و سوم خالصند )
در جواب بايدگفت بله مي‌توانيم. كافي است 4 مهره را به دو دسته تقسيم كنيم، 3 مهره دسته‌ي اول و يك مهره در دسته‌ي دوم. سه مهره‌ي دسته‌ي اول را با يك بار وزن كردن با سه مهره‌ي خالص از 27 مهره‌ي خالصي كه بدست آورده بوديم، مقايسه مي‌كنيم. دو حالت رخ خواهد داد. يا با هم هم وزن مي‌شوند كه در اين صورت مهره موجود در دسته دوم مهره نا خالص است و با چهارمين وزن كردن خواهيم فهميد كه از ساير مهره‌ها سنگين‌تر است يا سبك‌تر.
درحالت ديگر ممكن است، سه مهره‌ي دسته اول با سه مهره خالص هم وزن نباشند، مثلاً سنگين‌تر باشند. در اين صورت خواهيم دانست كه مهره‌ي نا خالص يكي از اين سه مهره است و از ساير مهره ها سنگين‌تر و همان‌طور كه قبلاً نيز ذكر شد با يك‌بار وزن كردن مهره نا خالص مشخص خواهد شد و به اين شكل مسئله اصلي حل شد.
اگر دانش آموز خلاقي اين مقاله را به دقت مطالعه كرده باشد و الگوريتم مطرح شده را كاملاً درك كند، احتمالاً مي‌تواند اين مسئله را براي حالتي كه مي‌خواهيم با پنج‌بار وزن كردن يك مهره نا خالص را از بين 94 مهره پيدا كرده بگوييم از ساير مهره‌ها سنگين تر است يا سبك تر نيز حل كند، و حتي شايد اثبات كند كه به طور كلي با n بار وزن كردن مي‌توان يك مهره نا خالص را از بين مهره يافته تعيين كرد كه از ساير مهره‌ها سنگين‌تر است يا سبك‌تر.
نظرات شما عزیزان:
